package FloodFill;

import 数组和链表.arraylist.ArrayList;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @description: 动态规划问题
 * @author: ywk
 * @date: 2021-01-02
 */
public class 信封嵌套问题 {
    //最长递增子序列:5,1,4,3,4,2 输出1，3，4
    static int LCS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length, max = 1;
        int [] d = new int[n];
        d[0] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int cur = nums[i] > nums[j] ? d[j] + 1 : 1;
                d[i] = Math.max(d[i], cur);
            }
            max = Math.max(max, d[i]);
        }
        return max;
    }

    //动态规划和二分法
    public static int lengthOfLISA(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] h = new int[nums.length];
        h[0] = nums[0];
        int max = 0;//最长子序列最右边的位置
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > h[max]) {
                h[++max] = nums[i];
                continue;
            } else {
                int pos = findFirstBigger(h, 0, max, nums[i]);
                h[pos] = nums[i];
            }
        }
        return max + 1;
    }

    public static int findFirstBigger(int[] h, int left, int right, int target) {
        if (left == right)
            return left;
        int mid = (left + right) / 2;
        if (h[mid] < target)
            return findFirstBigger(h, mid + 1, right, target);
        else
            return findFirstBigger(h, left, mid, target);
    }


    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        // 按宽度升序排列，如果宽度⼀样，则按⾼度降序排列
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        // 对⾼度数组寻找 LIS
        int[] height = new int[n];
        for (int i = 0; i < n; i++) height[i] = envelopes[i][1];
        return lengthOfLIS(height);
    }

    /* 返回 nums 中 LIS 的⻓度 */
    public static int lengthOfLIS(int[] nums) {
        int piles = 0, n = nums.length;
        int[] dp = new int[n];
        int[] top = new int[n];
        for (int i = 0; i < n; i++) {
            // 要处理的扑克牌
            int poker = nums[i];
            int left = 0, right = piles;
            // ⼆分查找插⼊位置
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] >= poker)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
            dp[i] = left;
        }
        // 牌堆数就是 LIS ⻓度
        //最长递增子序列:5,1,4,3,4,2 输出1，3，4

        int[] res = new int[piles];
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == piles)
                res[--piles] = nums[i];
        }
        return piles;
    }

    public static void main(String[] args) {
        System.out.println(LCS(new int[]{4, 5, 6, 1, 5, 2}));
        lengthOfLISA(new int[]{4, 5,  1, 2, 3});
        System.out.println(lengthOfLIS(new int[]{4, 5,  1, 2, 3}));
    }
}
